package com.zp.self.module.level_4_算法练习.数学.位运算;

/**
 * @author By ZengPeng
 */
public class 力扣_476_数字的补数 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_476_数字的补数().findComplement(5));
        System.out.println(new 力扣_476_数字的补数().findComplement(1));
    }

    /**
     * 题目：对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。
     *
     * 例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。
     * 给你一个整数 num ，输出它的补数。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：num = 5
     * 输出：2
     * 解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
     * 示例 2：
     *
     * 输入：num = 1
     * 输出：0
     * 解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
     *
     *
     * 分析：【Good】
     *      1. 直接异或 他的最高位 【开始没做出来】 num ^ 11111
     *      2. 通过栈 来反向
     *
     * 边界值 & 注意点：
     *      1.
     **/
    public int findComplement(int num) {
        //1. 直接异或 他的最高位 【开始没做出来】
        int  all_1 = 0;int init =num;
        while (num>0){
            all_1 = all_1<<1;
            all_1++;
            num= num>>1;
        }
        return init^all_1;

        //2. 通过栈 来反向
        /*Stack<Integer> stack = new Stack<>();
        while (num>0){
            if((num &1)==1)stack.push(0);
            else stack.push(1);
            num = num>>1;
        }

        while (!stack.isEmpty()){
           num=num<<1;
           if(stack.pop()==1) num++;
        }
        return num;*/
    }
}
